\subsection{数学归纳法}\label{subsec:2-4}

在第 \ref{subsec:2-2} 节中，我们是这样推导首项为 $a_1$，公差为 $d$ 的等差数列 $\{a_n\}$ 的通项公式的：

\begin{align*}
    &a_1 = a_1 = a_1 + 0d, \\
    &a_2 = a_1 + d = a_1 + 1d, \\
    &a_3 = a_2 + d = a_1 + 2d, \\
    &a_4 = a_3 + d = a_1 + 3d, \\
    &\cdots\cdots\cdots \qquad \cdots\cdots\cdots
\end{align*}

由此得到，等差数列 $\{a_n\}$ 的通项公式是
$$ a_n = a_1 + (n - 1)d \text{。} $$

象这种由一系列有限的特殊事例得出一般结论的推理方法，通常叫做\textbf{归纳法}。用归纳法可以帮助我们从具体事例中发现一般规律。
但是应该注意，仅根据一系列有限的特殊事例所得出的一般结论有时是不正确的。例如一个数列的通项公式是
$$ a_n = (n^2 - 5n + 5)^2 \text{，} $$
容易验证
$$ a_1 = 1,\quad a_2 = 1,\quad a_3 = 1,\quad a_4 = 1, $$
如果我们由此作出结论——对于任何 $n \in N$，$a_n = (n^2 - 5n + 5)^2 = 1$ 都成立，那就是错误的。
事实上， $a_5 = 25 \neq 1$。

对于由归纳法得到的某些与自然数有关的数学命题，我们常常采用下面的方法来证明它们的正确性：
先证明当 $n$ 取第一个值 $n_0$（例如 $n_0 = 1$）时命题成立，然后假设当 $n = k$ 时命题成立，
证明当 $n = k + 1$ 时命题也成立（因为证明了这一点，就可以断定这个命题对于 $n$ 取第一个值
后面的所有自然数也都成立）。这种证明方法叫做\textbf{数学归纳法}。

例如，我们用数学归纳法来证明：如果 $\{a_n\}$ 是一个等差数列，那么
$$ a_n = a_1 + (n - 1)d $$
对一切 $n \in N$ 都成立。

\zhengming （1） 当 $n = 1$ 时，左边是 $a_1$，右边是 $a_1 + 0d = a_1$ ，等式是成立的。

（2） 假设当 $n = k$ 时等式成立，就是
$$ a_k = a_1 + (k - 1)d \text{，} $$
那么，
\begin{align*}
    a_{k+1} &= a_k + d \\
            &= a_1 + (k - 1)d + d \\
            &= a_1 + [(k + 1) - 1]d \text{。}
\end{align*}

这就是说， 当 $n = k + 1$ 时，等式也成立。

根据（1），$n = 1$ 时等式成立， 再根据（2）， $n = 1 + 1 = 2$ 时等式也成立。
由于 $n = 2$ 时等式成立，再根据（2），$n = 2 + 1 = 3$ 时等式也成立。
这样递推下去， 就知道 $n = 4$，$5$，$6$，$\cdots$ 时等式都成立。
因此根据（1） 和 （2） 可以断定，等式对任何 $n \in N$ 都成立。

从上面的例子看到，用数学归纳法证明一个与自然数有关的命题的步骤是：

\textbf{（1）证明当 $n$ 取第一个值 $n_0$（ 例如 $n_0 = 1$ 或 $2$ 等） 时结论正确；}

\textbf{（2）假设当 $n = k \; (k \in N \text{，且} k \geqslant n_0)$ 时结论正确，证明当 $n = k + 1$ 时结论也正确。}

在完成了这两个步骤以后，就可以断定命题对于从 $n_0$ 开始的所有自然数 $n$ 都正确。

\textbf{例} \quad 用数学归纳法证明
$$ 1 + 3 + 5 + \cdots + (2n - 1) = n^2 \text{。} $$

\zhengming （1） 当 $n = 1$ 时， 左边$=1$， 右边$= 1$，等式成立。

（2） 假设当 $n = k$ 时等式成立，就是
$$ 1 + 3 + 5 + \cdots + (2k - 1) = k^2 \text{，} $$
那么，
\begin{align*}
      & 1 + 3 + 5 + \cdots + (2k - 1) + [2(k + 1) - 1] \\
    = & k^2 + [2(k + 1) - 1] \\
    = & k^2 + 2k + 1 \\
    = & (k + 1)^2 \text{。}
\end{align*}

这就是说，当 $n = k + 1$ 时等式也成立。

根据（1）和（2），可知等式对任何 $n \in N$ 都成立。

\begin{wrapfigure}[17]{r}{5cm}
    \centering
    \input{../pic/ds2-ch2-7}
    \caption{}\label{fig:2-7}
\end{wrapfigure}


本例所证明的等式可以用图 \ref{fig:2-7} 表示出来。

用数学归纳法证明命题的这两个步骤，是缺一不可的。从上面计算数列 $\{a_n\}$（其中 $a_n = (n^2 - 5n + 5)^2$）
各项的值可以看到，只完步骤（1） 而缺少步骤（2），就可能得出不正确的结论，因为单靠步骤（1），我们无法递推下去，
所以，对于取 $2$，$3$，$4$，$5$，$\cdots$ 时命题是否正确，我们无法判定。同样，只有步骤（2）而缺少步骤（1），
也可能得出不正确结论。例如，假设 $n = k$ 时，等式
$$ 2 + 4 + 6 + \cdots + 2n = n^2 + n + 1 $$
成立，就是
$$ 2 + 4 + 6 + \cdots + 2k = k^2 + k + 1 \text{，} $$
那么，
\begin{align*}
      & 2 + 4 + 6 + \cdots + 2k + 2(k + 1) \\
    = & k^2 + k + 1 + 2(k + 1) \\
    = & (k + 1)^2 + (k + 1) + 1 \text{。}
\end{align*}

这就是说，如果 $n = k$ 时等式成立，那么 $n = k + 1$ 时等式也成立。但如果仅根据这一步就得出等式对于任何 $n \in N$
都成立的结论，那就错了。事实上，当 $n = 1$ 时，上式左边 $= 2$，右边 $= 1^2 + 1 + 1 = 3$， 左边 $\neq$ 右边。
这也说明，如果缺少步骤（1）这个基础， 步骤（2）就没有意义了。

\lianxi

用数学归纳法证明：

\begin{xiaotis}

\xiaoti{$1 + 2 + 3 + \cdots + n = \dfrac{1}{2}n(n + 1)$。}

\xiaoti{$1 + 2 + 2^2 + \cdots + 2^{n -1} = 2^n - 1$。}

\xiaoti{首项是 $a_1$，公比是 $q$ 的等比数列的通项公式是
    $$ a_n = a_1 q^{n - 1} \text{。} $$
}

\end{xiaotis}

